/*
 * @lc app=leetcode.cn id=155 lang=cpp
 *
 * [155] 最小栈
 */

// @lc code=start
class MinStack {
public:
    /** initialize your data structure here. */
    //单调栈
    //来了一个新的小的数，则进栈
    //这样小的数一直在单调栈的栈顶；
    //相等时候也要进栈，因为pop时候判等即删除
    //如果比栈顶元素大，肯定比当前的最小值更早被pop掉，所以不可能是答案
    
    stack<int> minstack;
    stack<int> s;

    MinStack() {
 
    }
    
    void push(int x) {
        s.push(x);
        if(minstack.empty() || x <= minstack.top())
            minstack.push(x);
    }
    
    void pop() {
        int t = s.top();
        s.pop();
        if(minstack.top() == t) minstack.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return minstack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
// @lc code=end

